<!DOCTYPE html><html lang="zh"><head><meta charset="utf-8"><meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1,minimum-scale=1,user-scalable=no,minimal-ui"><meta name="renderer" content="webkit"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><meta name="apple-mobile-web-app-capable" content="yes"><meta name="apple-mobile-web-app-status-bar-style" content="black"><meta name="format-detection" content="telephone=no,email=no,adress=no"><meta name="theme-color" content="#000000"><meta http-equiv="window-target" content="_top"><title>Blog</title><meta name="description" content="前言 本来是想用C语言好好写的，可是指针和结构体太烦人了，弄得我头凉。因此决定用python实现一下图的一些算法。 远程仓库地址： https:&#x2F;&#x2F;github.com&#x2F;XiaoZhong233&#x2F;DataStructure_Python&#x2F;tree&#x2F;master&#x2F;graph  图的存储结构实现 图的实现有邻接矩阵，邻接表，十字链表等。我后面的算法主要用邻接表 建议直接看 [邻接表实现2，基于字典实"><meta property="og:type" content="article"><meta property="og:title" content="Zhong&#39;s blog"><meta property="og:url" content="http://xiaozhong233.gitee.io/2020/11/19/%E5%9B%BE%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%EF%BC%88%E6%B1%87%E6%80%BB%EF%BC%89/index.html"><meta property="og:site_name" content="Zhong&#39;s blog"><meta property="og:description" content="前言 本来是想用C语言好好写的，可是指针和结构体太烦人了，弄得我头凉。因此决定用python实现一下图的一些算法。 远程仓库地址： https:&#x2F;&#x2F;github.com&#x2F;XiaoZhong233&#x2F;DataStructure_Python&#x2F;tree&#x2F;master&#x2F;graph  图的存储结构实现 图的实现有邻接矩阵，邻接表，十字链表等。我后面的算法主要用邻接表 建议直接看 [邻接表实现2，基于字典实"><meta property="og:locale" content="zh_CN"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyNTE2MDMwNS5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyNTE2MDMwNS5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyOTE4MzM1OC5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyNTE2MDMwNS5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMDIyNDIzOS5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTAwMjYzNC5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyNTE2MDMwNS5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTE5MDkzNy5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTE5MzUyMC5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTE5MzUyMC5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTIwNTYzMi5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTIxMDUwMS5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTIxMjIzNi5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8xNTY3MjU3ODM1OTQ5LnBuZyFibG9n?x-oss-process=image/format,png"><meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTIxMjUwNC5wbmchYmxvZw?x-oss-process=image/format,png"><meta property="article:published_time" content="2020-11-19T02:28:04.862Z"><meta property="article:modified_time" content="2020-11-19T02:28:12.424Z"><meta property="article:author" content="钟浩伟"><meta name="twitter:card" content="summary"><meta name="twitter:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyNTE2MDMwNS5wbmchYmxvZw?x-oss-process=image/format,png"><link rel="canonical" href="http://xiaozhong233.gitee.io/2020/11/19/%E5%9B%BE%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%EF%BC%88%E6%B1%87%E6%80%BB%EF%BC%89/index.html"><link rel="alternate" href="/atom.xml" title="Zhong&#39;s blog" type="application/atom+xml"><link rel="icon" href="/favicon.png" type="image/x-icon"><link rel="stylesheet" href="/css/style.css"><link rel="stylesheet" href="//cdn.jsdelivr.net/npm/gitment@0.0.3/style/default.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hexo-math@4.0.0/dist/style.css"><meta name="generator" content="Hexo 5.2.0"></head><body class="main-center" itemscope itemtype="http://schema.org/WebPage"><header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="slimContent"><div class="navbar-header"><div class="profile-block text-center"><a id="avatar" href="https://github.com/XiaoZhong233" target="_blank"><img class="img-circle img-rotate" src="/images/avatar.jpg" width="200" height="200"></a><h2 id="name" class="hidden-xs hidden-sm">钟</h2><h3 id="title" class="hidden-xs hidden-sm hidden-md">苦逼学生仔 &amp; 未来搬砖大师</h3><small id="location" class="text-muted hidden-xs hidden-sm"><i class="icon icon-map-marker"></i> GuangZhou, China</small></div><div class="search" id="search-form-wrap"><form class="search-form sidebar-form"><div class="input-group"><input type="text" class="search-form-input form-control" placeholder="搜索"> <span class="input-group-btn"><button type="submit" class="search-form-submit btn btn-flat" onclick="return!1"><i class="icon icon-search"></i></button></span></div></form><div class="ins-search"><div class="ins-search-mask"></div><div class="ins-search-container"><div class="ins-input-wrapper"><input type="text" class="ins-search-input" placeholder="想要查找什么..." x-webkit-speech> <button type="button" class="close ins-close ins-selectable" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button></div><div class="ins-section-wrapper"><div class="ins-section-container"></div></div></div></div></div><button class="navbar-toggle collapsed" type="button" data-toggle="collapse" data-target="#main-navbar" aria-controls="main-navbar" aria-expanded="false"><span class="sr-only">Toggle navigation</span> <span class="icon-bar"></span> <span class="icon-bar"></span> <span class="icon-bar"></span></button></div><nav id="main-navbar" class="collapse navbar-collapse" itemscope itemtype="http://schema.org/SiteNavigationElement" role="navigation"><ul class="nav navbar-nav main-nav"><li class="menu-item menu-item-home"><a href="/."><i class="icon icon-home-fill"></i> <span class="menu-title">首页</span></a></li><li class="menu-item menu-item-archives"><a href="/archives"><i class="icon icon-archives-fill"></i> <span class="menu-title">归档</span></a></li><li class="menu-item menu-item-categories"><a href="/categories"><i class="icon icon-folder"></i> <span class="menu-title">分类</span></a></li><li class="menu-item menu-item-tags"><a href="/tags"><i class="icon icon-tags"></i> <span class="menu-title">标签</span></a></li><li class="menu-item menu-item-repository"><a href="/repository"><i class="icon icon-project"></i> <span class="menu-title">项目</span></a></li><li class="menu-item menu-item-about"><a href="/about"><i class="icon icon-cup-fill"></i> <span class="menu-title">关于</span></a></li></ul><ul class="social-links"><li><a href="https://github.com/XiaoZhong233" target="_blank" title="Github" data-toggle="tooltip" data-placement="top"><i class="icon icon-github"></i></a></li><li><a href="/atom.xml" target="_blank" title="Rss" data-toggle="tooltip" data-placement="top"><i class="icon icon-rss"></i></a></li></ul></nav></div></header><aside class="sidebar" itemscope itemtype="http://schema.org/WPSideBar"><div class="slimContent"><div class="widget"><h3 class="widget-title">公告</h3><div class="widget-body"><div id="board"><div class="content"><p>欢迎交流与分享经验!</p></div></div></div></div><div class="widget"><h3 class="widget-title">分类</h3><div class="widget-body"><ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/Python/">Python</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E5%90%8E%E7%AB%AF/">后端</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%90%86%E8%AE%BA/">计算机理论</a><span class="category-list-count">9</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E8%BF%90%E7%BB%B4/">运维</a><span class="category-list-count">1</span></li></ul></div></div><div class="widget"><h3 class="widget-title">标签</h3><div class="widget-body"><ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/tags/SpringCloud/" rel="tag">SpringCloud</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/python-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag">python,数据结构</a><span class="tag-list-count">7</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag">数据结构</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E6%B5%8B%E8%AF%95/" rel="tag">测试</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E7%88%AC%E8%99%AB/" rel="tag">爬虫</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E8%AF%BE%E5%A4%96%E7%9F%A5%E8%AF%86/" rel="tag">课外知识</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E9%83%A8%E7%BD%B2/" rel="tag">部署</a><span class="tag-list-count">1</span></li></ul></div></div><div class="widget"><h3 class="widget-title">标签云</h3><div class="widget-body tagcloud"><a href="/tags/SpringCloud/" style="font-size:13px">SpringCloud</a> <a href="/tags/python-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size:14px">python,数据结构</a> <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size:13.5px">数据结构</a> <a href="/tags/%E6%B5%8B%E8%AF%95/" style="font-size:13px">测试</a> <a href="/tags/%E7%88%AC%E8%99%AB/" style="font-size:13px">爬虫</a> <a href="/tags/%E8%AF%BE%E5%A4%96%E7%9F%A5%E8%AF%86/" style="font-size:13px">课外知识</a> <a href="/tags/%E9%83%A8%E7%BD%B2/" style="font-size:13px">部署</a></div></div><div class="widget"><h3 class="widget-title">归档</h3><div class="widget-body"><ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/11/">十一月 2020</a><span class="archive-list-count">6</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/01/">一月 2020</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/12/">十二月 2019</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/09/">九月 2019</a><span class="archive-list-count">9</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/08/">八月 2019</a><span class="archive-list-count">2</span></li></ul></div></div><div class="widget"><h3 class="widget-title">最新文章</h3><div class="widget-body"><ul class="recent-post-list list-unstyled no-thumbnail"><li><div class="item-inner"><p class="item-category"></p><p class="item-title"><a href="/2020/11/19/React%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93/" class="title">(no title)</a></p><p class="item-date"><time datetime="2020-11-19T02:31:19.165Z" itemprop="datePublished">2020-11-19</time></p></div></li><li><div class="item-inner"><p class="item-category"></p><p class="item-title"><a href="/2020/11/19/%E5%9B%BE%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%EF%BC%88%E6%B1%87%E6%80%BB%EF%BC%89/" class="title">(no title)</a></p><p class="item-date"><time datetime="2020-11-19T02:28:04.862Z" itemprop="datePublished">2020-11-19</time></p></div></li><li><div class="item-inner"><p class="item-category"></p><p class="item-title"><a href="/2020/11/19/%E6%B5%85%E8%B0%88%E5%8C%BA%E5%9D%97%E9%93%BE%E7%9A%84%E5%AF%86%E7%A0%81%E5%AD%A6%E5%8E%9F%E7%90%86_hash%E4%B8%8E%E7%AD%BE%E5%90%8D/" class="title">&#39;浅谈区块链的密码学原理:hash与签名&#39;</a></p><p class="item-date"><time datetime="2020-11-18T18:04:23.000Z" itemprop="datePublished">2020-11-19</time></p></div></li><li><div class="item-inner"><p class="item-category"></p><p class="item-title"><a href="/2020/11/19/hello/" class="title">hello</a></p><p class="item-date"><time datetime="2020-11-18T18:01:09.000Z" itemprop="datePublished">2020-11-19</time></p></div></li><li><div class="item-inner"><p class="item-category"></p><p class="item-title"><a href="/2020/11/19/%E6%AF%8F%E6%97%A5%E4%B8%80%E9%A2%98-%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F/" class="title">每日一题-岛屿数量</a></p><p class="item-date"><time datetime="2020-11-18T16:23:34.494Z" itemprop="datePublished">2020-11-19</time></p></div></li></ul></div></div></div></aside><main class="main" role="main"><div class="content"><article id="post-图的常见算法实现（汇总）" class="article article-type-post" itemscope itemtype="http://schema.org/BlogPosting"><div class="article-header"><div class="article-meta"><span class="article-date"><i class="icon icon-calendar-check"></i> <a href="/2020/11/19/%E5%9B%BE%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%EF%BC%88%E6%B1%87%E6%80%BB%EF%BC%89/" class="article-date"><time datetime="2020-11-19T02:28:04.862Z" itemprop="datePublished">2020-11-19</time> </a></span><span class="post-comment"><i class="icon icon-comment"></i> <a href="/2020/11/19/%E5%9B%BE%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%EF%BC%88%E6%B1%87%E6%80%BB%EF%BC%89/#comments" class="article-comment-link">评论</a></span></div></div><div class="article-entry marked-body" itemprop="articleBody"><h1 id="前言"><a class="markdownIt-Anchor" href="#前言"></a> 前言</h1><p>本来是想用C语言好好写的，可是指针和结构体太烦人了，弄得我头凉。因此决定用python实现一下图的一些算法。</p><p>远程仓库地址：</p><p><a target="_blank" rel="noopener" href="https://github.com/XiaoZhong233/DataStructure_Python/tree/master/graph">https://github.com/XiaoZhong233/DataStructure_Python/tree/master/graph</a></p><h1 id="图的存储结构实现"><a class="markdownIt-Anchor" href="#图的存储结构实现"></a> 图的存储结构实现</h1><p>图的实现有邻接矩阵，邻接表，十字链表等。我后面的算法主要用邻接表</p><p>建议直接看</p><p>[邻接表实现2，基于字典实现](# 邻接表实现2 (基于字典实现，好用))</p><p>首先定义了一个异常类：</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">GraphError</span>(<span class="params">Exception</span>):</span></span><br><span class="line">    <span class="keyword">pass</span></span><br></pre></td></tr></table></figure><h2 id="邻接矩阵实现"><a class="markdownIt-Anchor" href="#邻接矩阵实现"></a> 邻接矩阵实现</h2><p>基于邻接矩阵定义了一个实现图的类，其中矩阵元素可以是1或者其他权值，表示有边，或者用一个特殊值表示“无关联”。构造参数的<code>unconn</code>就是表示无关联的值，默认为0。</p><p>图的构造函数的主要参数是<code>mat</code>,表示初始的邻接矩阵。要求是一个二维数组，且为方阵。代码如下</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># unconn 无关联参数</span></span><br><span class="line"><span class="comment"># 邻接矩阵实现</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Graph</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self, mat, unconn=<span class="number">0</span></span>):</span></span><br><span class="line">        vnum = <span class="built_in">len</span>(mat)</span><br><span class="line">        <span class="comment"># 检查是否为方阵</span></span><br><span class="line">        <span class="keyword">for</span> x <span class="keyword">in</span> mat:</span><br><span class="line">            <span class="keyword">if</span> <span class="built_in">len</span>(x) != vnum:</span><br><span class="line">                <span class="keyword">raise</span> ValueError(<span class="string">&quot;参数错误：不为方阵&quot;</span>)</span><br><span class="line">        <span class="comment"># 拷贝数据</span></span><br><span class="line">        self._mat = [mat[i][:] <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(vnum)]</span><br><span class="line">        self._unconn = unconn</span><br><span class="line">        self._vnum = vnum</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 返回顶点数目</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">vertex_num</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="keyword">return</span> self._vnum</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 检查该顶点是否合法，也就是下标是否找得到</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">_invalid</span>(<span class="params">self, v</span>):</span></span><br><span class="line">        <span class="keyword">return</span> v &lt; <span class="number">0</span> <span class="keyword">or</span> v &gt;= self._vnum</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 加入新的顶点</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_vertex</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">&quot;邻接矩阵不支持加入顶点&quot;</span>)</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 加入新的边</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_edge</span>(<span class="params">self, vi, vj, val=<span class="number">1</span></span>):</span></span><br><span class="line">        <span class="keyword">if</span> self._invalid(vi) <span class="keyword">or</span> self._invalid(vj):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">&quot;顶点不合法&quot;</span>)</span><br><span class="line">        self._mat[vi][vj] = val</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 获得某条边</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">get_edge</span>(<span class="params">self, vi, vj</span>):</span></span><br><span class="line">        <span class="keyword">if</span> self._invalid(vi) <span class="keyword">or</span> self._invalid(vj):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">&quot;顶点不合法&quot;</span>)</span><br><span class="line">        <span class="keyword">return</span> self._mat[vi][vj]</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 获得某个顶点的出边</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">out_edges</span>(<span class="params">self, vi</span>):</span></span><br><span class="line">        <span class="keyword">if</span> self._invalid(vi):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">&quot;顶点不合法&quot;</span>)</span><br><span class="line">        <span class="keyword">return</span> self.out_edge(self._mat[vi], self._unconn)</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 获得某个顶点的出边</span></span><br><span class="line"><span class="meta">    @staticmethod</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">_out_edges</span>(<span class="params">row, unconn</span>):</span></span><br><span class="line">        edges = []</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(row)):</span><br><span class="line">            <span class="keyword">if</span> row[i] != unconn:</span><br><span class="line">                edges.append((i, row[i]))</span><br><span class="line">        <span class="keyword">return</span> edges</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__str__</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="keyword">return</span> <span class="string">&quot;[\n&quot;</span> + <span class="string">&quot;,\n&quot;</span>.join(<span class="built_in">map</span>(<span class="built_in">str</span>, self._mat)) + <span class="string">&quot;\n]&quot;</span> \</span><br><span class="line">               + <span class="string">&quot;\nUnconnected: &quot;</span> + <span class="built_in">str</span>(self._unconn)</span><br><span class="line"></span><br></pre></td></tr></table></figure><p>这个简单的邻接矩阵实现的图类并未支持增加顶点，因为邻接矩阵增加顶点要增加多一行一列，挺麻烦的，就不想写了。</p><h2 id="邻接表实现1基于邻接矩阵不好用"><a class="markdownIt-Anchor" href="#邻接表实现1基于邻接矩阵不好用"></a> 邻接表实现1（基于邻接矩阵，不好用）</h2><p>邻接矩阵的缺点是占用空间很多，如果是稀疏图就很难受了，可能会有很大的空间损失，因此常用邻接表实现图的存储。在上面邻接矩阵的实现下，可考虑一种“压缩后”的邻接表实现。</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"># 邻接表实现（压缩邻接矩阵形式）</span><br><span class="line">class GraphAL(Graph):</span><br><span class="line">    def __init__(self, mat&#x3D;[], unconn&#x3D;0):</span><br><span class="line">        vnum &#x3D; len(mat)</span><br><span class="line">        for x in mat:</span><br><span class="line">            if len(x) !&#x3D; vnum:</span><br><span class="line">                raise ValueError(&quot;参数错误：不为方阵&quot;)</span><br><span class="line">        self._mat &#x3D; [Graph._out_edges(mat[i], unconn) for i in range(vnum)]</span><br><span class="line">        self._vnum &#x3D; vnum</span><br><span class="line">        self._unconn &#x3D; unconn</span><br><span class="line"></span><br><span class="line">    def add_vertex(self):</span><br><span class="line">        self._mat.append([])</span><br><span class="line">        self._vnum +&#x3D; 1</span><br><span class="line">        return self._vnum - 1</span><br><span class="line"></span><br><span class="line">    def add_edge(self, vi, vj, val&#x3D;1):</span><br><span class="line">        if self._vnum &#x3D;&#x3D; 0:</span><br><span class="line">            raise GraphError(&quot;无法为空图增加边&quot;)</span><br><span class="line">        if self._invalid(vi) or self._invalid(vj):</span><br><span class="line">            raise GraphError(&quot;顶点不合法&quot;)</span><br><span class="line"></span><br><span class="line">        row &#x3D; self._mat[vi]</span><br><span class="line">        i &#x3D; 0</span><br><span class="line">        while i &lt; len(row):</span><br><span class="line">            if row[i][0] &#x3D;&#x3D; vj:</span><br><span class="line">                self._mat[vi][i] &#x3D; (vj, val)</span><br><span class="line">                return</span><br><span class="line">            if row[i][0] &gt; vj:  # 没有到与vj的边，退出循环加入边</span><br><span class="line">                break</span><br><span class="line">            i +&#x3D; 1</span><br><span class="line">        self._mat[vi].insert(i, (vj, val))</span><br><span class="line"></span><br><span class="line">    def get_edge(self, vi, vj):</span><br><span class="line">        if self._invalid(vi) or self._invalid(vj):</span><br><span class="line">            raise GraphError(&quot;顶点不合法&quot;)</span><br><span class="line">        for i, val in self._mat[vi]:</span><br><span class="line">            if i &#x3D;&#x3D; vj:</span><br><span class="line">                return val</span><br><span class="line">        return self._unconn</span><br><span class="line"></span><br><span class="line">    def out_edges(self, vi):</span><br><span class="line">        if self._invalid(vi):</span><br><span class="line">            raise GraphError(&quot;顶点不合法&quot;)</span><br><span class="line">        return self._mat[vi]</span><br></pre></td></tr></table></figure><h2 id="邻接表实现2-基于字典实现后面的算法都以此作为存储结构"><a class="markdownIt-Anchor" href="#邻接表实现2-基于字典实现后面的算法都以此作为存储结构"></a> 邻接表实现2 (基于字典实现，后面的算法都以此作为存储结构)</h2><p>新建一个<code>GraphAL.py</code>文件，在文件中添加：</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 邻接表实现无向网（图）（字典形式）</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">GraphAL</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self, graph=&#123;&#125;</span>):</span></span><br><span class="line">        self._graph = graph</span><br><span class="line">        self._vnum = <span class="built_in">len</span>(graph)</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">_invalid</span>(<span class="params">self, vertex</span>):</span></span><br><span class="line">        <span class="keyword">return</span> self._graph.__contains__(vertex)</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_vertex</span>(<span class="params">self, vertex</span>):</span></span><br><span class="line">        <span class="keyword">if</span> self._invalid(vertex):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">&quot;添加顶点失败，已经有该顶点&quot;</span>)</span><br><span class="line">        self._graph[vertex] = &#123;&#125;</span><br><span class="line">        self._vnum += <span class="number">1</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_edge</span>(<span class="params">self, vi, vj, val</span>):</span></span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(vi) <span class="keyword">or</span> <span class="keyword">not</span> self._invalid(vj):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">&quot;不存在&quot;</span> + vi + <span class="string">&quot;或者&quot;</span> + vj + <span class="string">&quot;这样的顶点&quot;</span>)</span><br><span class="line">        self._graph[vi].update(&#123;vj: val&#125;)</span><br><span class="line">        self._graph[vj].update(&#123;vi: val&#125;)</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">get_edge</span>(<span class="params">self, vi, vj</span>):</span></span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(vi) <span class="keyword">or</span> <span class="keyword">not</span> self._invalid(vj):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">&quot;不存在&quot;</span> + vi + <span class="string">&quot;或者&quot;</span> + vj + <span class="string">&quot;这样的顶点&quot;</span>)</span><br><span class="line">        <span class="keyword">return</span> self._graph[vi][vj]</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">get_vertexNum</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="keyword">return</span> self._graph.__len__()</span><br><span class="line"></span><br><span class="line">    <span class="comment"># 在无向网（图）中是边，有向网（图）是出边，取决于数据</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">out_edge</span>(<span class="params">self, vertex</span>):</span></span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(vertex):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">&quot;不存在&quot;</span> + vertex + <span class="string">&quot;这样的顶点&quot;</span>)</span><br><span class="line">        <span class="keyword">return</span> self._graph[vertex]</span><br><span class="line">    </span><br><span class="line">    </span><br></pre></td></tr></table></figure><p>你也可以不传入图的参数，会默认创建一个新图。通过<code>add_vertex</code>和<code>add_edge</code>即可完成图的构建。</p><p>数据格式如下所示：</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">graph = &#123;</span><br><span class="line">    <span class="string">&quot;A&quot;</span>: &#123;<span class="string">&quot;B&quot;</span>: <span class="number">5</span>, <span class="string">&quot;C&quot;</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">&quot;B&quot;</span>: &#123;<span class="string">&quot;A&quot;</span>: <span class="number">5</span>, <span class="string">&quot;C&quot;</span>: <span class="number">2</span>, <span class="string">&quot;D&quot;</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">&quot;C&quot;</span>: &#123;<span class="string">&quot;A&quot;</span>: <span class="number">1</span>, <span class="string">&quot;B&quot;</span>: <span class="number">2</span>, <span class="string">&quot;D&quot;</span>: <span class="number">4</span>, <span class="string">&quot;E&quot;</span>: <span class="number">8</span>&#125;,</span><br><span class="line">    <span class="string">&quot;D&quot;</span>: &#123;<span class="string">&quot;B&quot;</span>: <span class="number">1</span>, <span class="string">&quot;C&quot;</span>: <span class="number">4</span>, <span class="string">&quot;E&quot;</span>: <span class="number">3</span>, <span class="string">&quot;F&quot;</span>: <span class="number">6</span>&#125;,</span><br><span class="line">    <span class="string">&quot;E&quot;</span>: &#123;<span class="string">&quot;C&quot;</span>: <span class="number">8</span>, <span class="string">&quot;D&quot;</span>: <span class="number">3</span>&#125;,</span><br><span class="line">    <span class="string">&quot;F&quot;</span>: &#123;<span class="string">&quot;D&quot;</span>: <span class="number">6</span>&#125;,</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyNTE2MDMwNS5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190825160305"><br>如上图所示，该类是一个无向网，如果需要改成有向网，只需要更改<code>add_edge</code>这个方法，修改为：</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">add_edge</span>(<span class="params">self, vi, vj, val</span>):</span></span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(vi) <span class="keyword">or</span> <span class="keyword">not</span> self._invalid(vj):</span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">&quot;不存在&quot;</span> + vi + <span class="string">&quot;或者&quot;</span> + vj + <span class="string">&quot;这样的顶点&quot;</span>)</span><br><span class="line">    self._graph[vi].update(&#123;vj: val&#125;)</span><br></pre></td></tr></table></figure><h1 id="图的一些算法实现"><a class="markdownIt-Anchor" href="#图的一些算法实现"></a> 图的一些算法实现</h1><h2 id="图的遍历"><a class="markdownIt-Anchor" href="#图的遍历"></a> 图的遍历</h2><h3 id="bfs广度优先搜索"><a class="markdownIt-Anchor" href="#bfs广度优先搜索"></a> BFS（广度优先搜索）</h3><h4 id="算法原理及步骤"><a class="markdownIt-Anchor" href="#算法原理及步骤"></a> 算法原理及步骤</h4><p>按照广度优先原则遍历图，利用了队列，有点像树的层次遍历。广度优先遍历的结果不唯一。整个遍历过程大概是这样的：给定一个起始顶点，将该起始顶点入队</p><ol><li>顶点出队，如果当前顶点未被标记访问，则访问该顶点，然后标记为已访问，如果当前顶点已访问则直接丢弃该顶点</li><li>当前访问顶点的邻接顶点入队</li><li>当队列不为空的时候，循环1,2步</li></ol><h4 id="算法流程"><a class="markdownIt-Anchor" href="#算法流程"></a> 算法流程</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	start(起始点入队)</span><br><span class="line">	deque[出队]</span><br><span class="line">	isVisit&#123;未被访问?&#125;</span><br><span class="line">	visit(访问该结点并输出)</span><br><span class="line">	isnull[检查队空]</span><br><span class="line">	end1((结束))</span><br><span class="line">	</span><br><span class="line">start--&gt;deque</span><br><span class="line">deque--&gt;isVisit</span><br><span class="line">isVisit--未被访问--&gt;visit</span><br><span class="line">isVisit--已经被访问--&gt;deque</span><br><span class="line">isnull--&gt;end1</span><br><span class="line">visit--&gt;isnull</span><br><span class="line">isnull--不为空--&gt;deque</span><br><span class="line">	</span><br></pre></td></tr></table></figure><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">flowchat</span><br><span class="line">st&#x3D;&gt;start: 初始化队列，初始顶点入队</span><br><span class="line">e&#x3D;&gt;end: 结束BFS</span><br><span class="line">deque&#x3D;&gt;operation: 出队</span><br><span class="line">isVisit&#x3D;&gt;condition: 是否访问过该顶点?</span><br><span class="line">visit&#x3D;&gt;inputoutput: 访问</span><br><span class="line">jump&#x3D;&gt;operation: 跳过该顶点的访问</span><br><span class="line">isqueNull&#x3D;&gt;condition: 是否队空</span><br><span class="line"></span><br><span class="line">st-&gt;deque-&gt;isVisit</span><br><span class="line">isVisit(yes)-&gt;jump-&gt;isqueNull</span><br><span class="line">isVisit(no)-&gt;visit-&gt;isqueNull</span><br><span class="line">isqueNull(yes)-&gt;e</span><br><span class="line">isqueNull(no)-&gt;deque</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure><h4 id="算法实现"><a class="markdownIt-Anchor" href="#算法实现"></a> 算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 广度优先遍历</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bfs</span>(<span class="params">self, start</span>):</span></span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(start):</span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">&quot;不存在&quot;</span> + start + <span class="string">&quot;这样的顶点&quot;</span>)</span><br><span class="line">    queue = [start]  <span class="comment"># 队列实现BFS</span></span><br><span class="line">    seen = <span class="built_in">set</span>(start)  <span class="comment"># 记录访问过的顶点</span></span><br><span class="line">    parent = &#123;start: <span class="literal">None</span>&#125;  <span class="comment"># Node代表根节点，数组形式保存树</span></span><br><span class="line">    result = []</span><br><span class="line">    <span class="keyword">while</span> queue.__len__() &gt; <span class="number">0</span>:  <span class="comment"># 队非空时</span></span><br><span class="line">        vertex = queue.pop(<span class="number">0</span>)  <span class="comment"># 队首顶点出队</span></span><br><span class="line">        nodes = self._graph[vertex]  <span class="comment"># 获得其邻接顶点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> nodes:</span><br><span class="line">            <span class="keyword">if</span> node <span class="keyword">not</span> <span class="keyword">in</span> seen:</span><br><span class="line">                queue.append(node)  <span class="comment"># 其邻接顶点如果没有被访问，则入队，并且保留父顶点</span></span><br><span class="line">                seen.add(node)</span><br><span class="line">                parent[node] = vertex</span><br><span class="line">        result.append(vertex)</span><br><span class="line">    <span class="keyword">return</span> result, parent</span><br></pre></td></tr></table></figure><h4 id="测试"><a class="markdownIt-Anchor" href="#测试"></a> 测试</h4><p>例如遍历下图</p><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyNTE2MDMwNS5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190825160305"></p><p>具体的存储结构为：</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">data = &#123;</span><br><span class="line">    <span class="string">&quot;A&quot;</span>: &#123;<span class="string">&quot;B&quot;</span>: <span class="number">5</span>, <span class="string">&quot;C&quot;</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">&quot;B&quot;</span>: &#123;<span class="string">&quot;A&quot;</span>: <span class="number">5</span>, <span class="string">&quot;C&quot;</span>: <span class="number">2</span>, <span class="string">&quot;D&quot;</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">&quot;C&quot;</span>: &#123;<span class="string">&quot;A&quot;</span>: <span class="number">1</span>, <span class="string">&quot;B&quot;</span>: <span class="number">2</span>, <span class="string">&quot;D&quot;</span>: <span class="number">4</span>, <span class="string">&quot;E&quot;</span>: <span class="number">8</span>&#125;,</span><br><span class="line">    <span class="string">&quot;D&quot;</span>: &#123;<span class="string">&quot;B&quot;</span>: <span class="number">1</span>, <span class="string">&quot;C&quot;</span>: <span class="number">4</span>, <span class="string">&quot;E&quot;</span>: <span class="number">3</span>, <span class="string">&quot;F&quot;</span>: <span class="number">6</span>&#125;,</span><br><span class="line">    <span class="string">&quot;E&quot;</span>: &#123;<span class="string">&quot;C&quot;</span>: <span class="number">8</span>, <span class="string">&quot;D&quot;</span>: <span class="number">3</span>&#125;,</span><br><span class="line">    <span class="string">&quot;F&quot;</span>: &#123;<span class="string">&quot;D&quot;</span>: <span class="number">6</span>&#125;,</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">test_bfs</span>(<span class="params">self</span>):</span></span><br><span class="line">    print(<span class="string">&quot;bfs测试：&quot;</span>)</span><br><span class="line">    bfs, bfsparent = TestGraph.g.bfs(<span class="string">&quot;A&quot;</span>)</span><br><span class="line">    print(<span class="string">&quot;BFS:&quot;</span> + graph.GraphAL.printPath(bfs))</span><br><span class="line">    print(<span class="string">&quot;BFS生成路径:&quot;</span> + bfsparent.__str__())</span><br><span class="line">    print(<span class="string">&quot;BFS生成路径打印：&quot;</span> + graph.GraphAL.printTreePath(bfsparent).__str__())</span><br><span class="line">    <span class="keyword">pass</span></span><br></pre></td></tr></table></figure><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyOTE4MzM1OC5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190829183358"></p><h3 id="dfs深度优先搜索"><a class="markdownIt-Anchor" href="#dfs深度优先搜索"></a> DFS（深度优先搜索）</h3><h4 id="算法原理及步骤-2"><a class="markdownIt-Anchor" href="#算法原理及步骤-2"></a> 算法原理及步骤</h4><p>DFS和BFS很像，不过DFS是深度优先的原则，具体实现是栈。</p><p>DFS遍历的结果不唯一。整个遍历过程大概是这样的：给定一个起始顶点，将该起始顶点入栈</p><ol><li>顶点出栈，如果当前顶点未被标记访问，则访问该顶点，然后标记为已访问，如果当前顶点已访问则直接丢弃该顶点</li><li>当前访问顶点的邻接顶点入栈</li><li>当栈不为空的时候，循环1,2步</li></ol><h4 id="算法流程-2"><a class="markdownIt-Anchor" href="#算法流程-2"></a> 算法流程</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	start(起始点入栈)</span><br><span class="line">	deque[出栈]</span><br><span class="line">	isVisit&#123;未被访问?&#125;</span><br><span class="line">	visit(访问该结点并输出)</span><br><span class="line">	isnull[检查栈空]</span><br><span class="line">	end1((结束))</span><br><span class="line">	</span><br><span class="line">start--&gt;deque</span><br><span class="line">deque--&gt;isVisit</span><br><span class="line">isVisit--未被访问--&gt;visit</span><br><span class="line">isVisit--已经被访问--&gt;deque</span><br><span class="line">isnull--&gt;end1</span><br><span class="line">visit--&gt;isnull</span><br><span class="line">isnull--不为空--&gt;deque</span><br></pre></td></tr></table></figure><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">flowchat</span><br><span class="line">st&#x3D;&gt;start: 初始化栈，初始顶点进栈</span><br><span class="line">e&#x3D;&gt;end: 结束DFS</span><br><span class="line">deque&#x3D;&gt;operation: 出栈</span><br><span class="line">isVisit&#x3D;&gt;condition: 是否访问过该顶点?</span><br><span class="line">visit&#x3D;&gt;inputoutput: 访问</span><br><span class="line">jump&#x3D;&gt;operation: 跳过该顶点的访问</span><br><span class="line">isqueNull&#x3D;&gt;condition: 是否栈空</span><br><span class="line"></span><br><span class="line">st-&gt;deque-&gt;isVisit</span><br><span class="line">isVisit(yes)-&gt;jump-&gt;isqueNull</span><br><span class="line">isVisit(no)-&gt;visit-&gt;isqueNull</span><br><span class="line">isqueNull(yes)-&gt;e</span><br><span class="line">isqueNull(no)-&gt;deque</span><br></pre></td></tr></table></figure><h4 id="算法实现-2"><a class="markdownIt-Anchor" href="#算法实现-2"></a> 算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 深度优先遍历</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">dfs</span>(<span class="params">self, start</span>):</span></span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(start):</span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">&quot;不存在&quot;</span> + start + <span class="string">&quot;这样的顶点&quot;</span>)</span><br><span class="line">    stack = [start]  <span class="comment"># 栈实现DFS</span></span><br><span class="line">    seen = <span class="built_in">set</span>(start)  <span class="comment"># 记录访问过的顶点</span></span><br><span class="line">    parent = &#123;start: <span class="literal">None</span>&#125;  <span class="comment"># Node代表根节点，数组形式保存树</span></span><br><span class="line">    result = []</span><br><span class="line">    <span class="keyword">while</span> stack.__len__() &gt; <span class="number">0</span>:  <span class="comment"># 栈非空时</span></span><br><span class="line">        vertex = stack.pop()  <span class="comment"># 顶点出栈</span></span><br><span class="line">        nodes = self._graph[vertex]  <span class="comment"># 获取出栈顶点的邻接顶点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> nodes:</span><br><span class="line">            <span class="keyword">if</span> node <span class="keyword">not</span> <span class="keyword">in</span> seen:</span><br><span class="line">                stack.append(node)</span><br><span class="line">                seen.add(node)</span><br><span class="line">                parent[node] = vertex</span><br><span class="line">        result.append(vertex)</span><br><span class="line">    <span class="keyword">return</span> result, parent</span><br></pre></td></tr></table></figure><h4 id="测试-2"><a class="markdownIt-Anchor" href="#测试-2"></a> 测试</h4><p>例如遍历下图</p><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyNTE2MDMwNS5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190825160305"></p><h5 id="存储结构"><a class="markdownIt-Anchor" href="#存储结构"></a> 存储结构</h5><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">data = &#123;</span><br><span class="line">    <span class="string">&quot;A&quot;</span>: &#123;<span class="string">&quot;B&quot;</span>: <span class="number">5</span>, <span class="string">&quot;C&quot;</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">&quot;B&quot;</span>: &#123;<span class="string">&quot;A&quot;</span>: <span class="number">5</span>, <span class="string">&quot;C&quot;</span>: <span class="number">2</span>, <span class="string">&quot;D&quot;</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">&quot;C&quot;</span>: &#123;<span class="string">&quot;A&quot;</span>: <span class="number">1</span>, <span class="string">&quot;B&quot;</span>: <span class="number">2</span>, <span class="string">&quot;D&quot;</span>: <span class="number">4</span>, <span class="string">&quot;E&quot;</span>: <span class="number">8</span>&#125;,</span><br><span class="line">    <span class="string">&quot;D&quot;</span>: &#123;<span class="string">&quot;B&quot;</span>: <span class="number">1</span>, <span class="string">&quot;C&quot;</span>: <span class="number">4</span>, <span class="string">&quot;E&quot;</span>: <span class="number">3</span>, <span class="string">&quot;F&quot;</span>: <span class="number">6</span>&#125;,</span><br><span class="line">    <span class="string">&quot;E&quot;</span>: &#123;<span class="string">&quot;C&quot;</span>: <span class="number">8</span>, <span class="string">&quot;D&quot;</span>: <span class="number">3</span>&#125;,</span><br><span class="line">    <span class="string">&quot;F&quot;</span>: &#123;<span class="string">&quot;D&quot;</span>: <span class="number">6</span>&#125;,</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h5 id="测试结果"><a class="markdownIt-Anchor" href="#测试结果"></a> 测试结果</h5><figure class="highlight"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">图的结构为：</span><br><span class="line">(<span class="string">&#x27;A&#x27;</span>, &#123;<span class="string">&#x27;B&#x27;</span>: <span class="number">5</span>, <span class="string">&#x27;C&#x27;</span>: <span class="number">1</span>&#125;)</span><br><span class="line">(<span class="string">&#x27;B&#x27;</span>, &#123;<span class="string">&#x27;A&#x27;</span>: <span class="number">5</span>, <span class="string">&#x27;C&#x27;</span>: <span class="number">2</span>, <span class="string">&#x27;D&#x27;</span>: <span class="number">1</span>&#125;)</span><br><span class="line">(<span class="string">&#x27;C&#x27;</span>, &#123;<span class="string">&#x27;A&#x27;</span>: <span class="number">1</span>, <span class="string">&#x27;B&#x27;</span>: <span class="number">2</span>, <span class="string">&#x27;D&#x27;</span>: <span class="number">4</span>, <span class="string">&#x27;E&#x27;</span>: <span class="number">8</span>&#125;)</span><br><span class="line">(<span class="string">&#x27;D&#x27;</span>, &#123;<span class="string">&#x27;B&#x27;</span>: <span class="number">1</span>, <span class="string">&#x27;C&#x27;</span>: <span class="number">4</span>, <span class="string">&#x27;E&#x27;</span>: <span class="number">3</span>, <span class="string">&#x27;F&#x27;</span>: <span class="number">6</span>&#125;)</span><br><span class="line">(<span class="string">&#x27;E&#x27;</span>, &#123;<span class="string">&#x27;C&#x27;</span>: <span class="number">8</span>, <span class="string">&#x27;D&#x27;</span>: <span class="number">3</span>&#125;)</span><br><span class="line">(<span class="string">&#x27;F&#x27;</span>, &#123;<span class="string">&#x27;D&#x27;</span>: <span class="number">6</span>&#125;)</span><br><span class="line"></span><br><span class="line">dfs测试：</span><br><span class="line">DFS:A-&gt;C-&gt;E-&gt;D-&gt;F-&gt;B</span><br><span class="line">DFS生成路径:&#123;<span class="string">&#x27;A&#x27;</span>: <span class="literal">None</span>, <span class="string">&#x27;B&#x27;</span>: <span class="string">&#x27;A&#x27;</span>, <span class="string">&#x27;C&#x27;</span>: <span class="string">&#x27;A&#x27;</span>, <span class="string">&#x27;D&#x27;</span>: <span class="string">&#x27;C&#x27;</span>, <span class="string">&#x27;E&#x27;</span>: <span class="string">&#x27;C&#x27;</span>, <span class="string">&#x27;F&#x27;</span>: <span class="string">&#x27;D&#x27;</span>&#125;</span><br><span class="line">DFS生成路径打印：</span><br><span class="line">A-&gt;B</span><br><span class="line">A-&gt;C</span><br><span class="line">A-&gt;C-&gt;D</span><br><span class="line">A-&gt;C-&gt;E</span><br><span class="line">A-&gt;C-&gt;D-&gt;F</span><br></pre></td></tr></table></figure><h2 id="最小生成树"><a class="markdownIt-Anchor" href="#最小生成树"></a> 最小生成树</h2><p>最小生成树针对的是连通网而言的。假定一个网络G，他的边带有权值，自然可以通过BFS,DFS获得他的生成树，权值最小的那棵树，就称最小生成树</p><p>最小生成树有许多实际的应用，例如通信网，输电网及各种网的规划。</p><h3 id="prim算法"><a class="markdownIt-Anchor" href="#prim算法"></a> Prim算法</h3><h4 id="算法原理及算法流程"><a class="markdownIt-Anchor" href="#算法原理及算法流程"></a> 算法原理及算法流程</h4><h5 id="原理"><a class="markdownIt-Anchor" href="#原理"></a> 原理：</h5><p>根据（MST性质：网络G必有一颗最小生成树），具体证明不再赘述，大概思想就是假设你现有一个图的集合G，从G中的一个顶点出发，不断的选择最短的一条连接边，扩充到已选边集N中，直至N包含了图G中的所有顶点。</p><h5 id="构造过程举例"><a class="markdownIt-Anchor" href="#构造过程举例"></a> 构造过程举例</h5><p>假设现在有这样一颗图</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">graph RL</span><br><span class="line">	V1((V1))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V5((V5))</span><br><span class="line">	V6((V6))</span><br><span class="line">V1--6---V2</span><br><span class="line">V1--1---V3</span><br><span class="line">V1--5---V4</span><br><span class="line">V2--5---V3</span><br><span class="line">V3--5---V4</span><br><span class="line">V3--6---V5</span><br><span class="line">V3--4---V6</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure><p>要对该图进行prim算法进行最小生成树。首先找一个开始顶点，假设从<code>V1</code>开始</p><h6 id="第一次构造"><a class="markdownIt-Anchor" href="#第一次构造"></a> 第一次构造</h6><p>V1的邻接节点全部入队。并且由于该队列是优先级队列，会按照权重排序</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V13((v1,v3,1))</span><br><span class="line">	V14((v1,v4,5))</span><br><span class="line">	V12((v1,v2,6))</span><br><span class="line">	</span><br><span class="line">V13--&gt;V14</span><br><span class="line">V14--&gt;V12</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure><p>队首出队，构造边，将该边加入到N集</p><p>此时N集中就有了一条边了</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">V1--1---V3</span><br></pre></td></tr></table></figure><p><code>V3</code>除了N集中的结点的邻接节点入队，优先队列会按照权重进行排序</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V32((v3,v2,5))</span><br><span class="line">	V34((v3,v4,5))</span><br><span class="line">	V35((v3,v5,6))</span><br><span class="line">	V36((v3,v6,4))</span><br><span class="line">	V14((v1,v4,5))</span><br><span class="line">	V12((v1,v2,6))</span><br><span class="line">V36--&gt;V14</span><br><span class="line">V14--&gt;V32</span><br><span class="line">V32--&gt;V34</span><br><span class="line">V34--&gt;V12</span><br><span class="line">V12--&gt;V35</span><br></pre></td></tr></table></figure><h6 id="第二次构造"><a class="markdownIt-Anchor" href="#第二次构造"></a> 第二次构造</h6><p>队首出队，构造边，将该边加入到N集</p><p>此时N集有两条边了</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">V1--1---V3</span><br><span class="line">V3--4---V6</span><br></pre></td></tr></table></figure><p>将<code>V6</code>的除N集中已有的邻接节点入队，</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V64((v6,v4,2))</span><br><span class="line">	V65((V6,V5,6))</span><br><span class="line">	V32((v3,v2,5))</span><br><span class="line">	V34((v3,v4,5))</span><br><span class="line">	V35((v3,v5,6))</span><br><span class="line">	V14((v1,v4,5))</span><br><span class="line">	V12((v1,v2,6))</span><br><span class="line">V64--&gt;V14</span><br><span class="line">V14--&gt;V32</span><br><span class="line">V32--&gt;V34</span><br><span class="line">V34--&gt;V12</span><br><span class="line">V12--&gt;V35</span><br><span class="line">V35--&gt;V65</span><br></pre></td></tr></table></figure><h6 id="第三次构造"><a class="markdownIt-Anchor" href="#第三次构造"></a> 第三次构造</h6><p>队首出队，构造边，将该边&lt;6,4&gt;加入到N集</p><p>此时的N集就有三条边了</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">V1--1---V3</span><br><span class="line">V3--4---V6</span><br><span class="line">V6--2---V4</span><br></pre></td></tr></table></figure><p>将<code>V4</code>的除N集中已有的邻接节点入队,发现v4的邻接顶点都在N集中了，所以没有顶点入队</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V65((V6,V5,6))</span><br><span class="line">	V32((v3,v2,5))</span><br><span class="line">	V34((v3,v4,5))</span><br><span class="line">	V35((v3,v5,6))</span><br><span class="line">	V14((v1,v4,5))</span><br><span class="line">	V12((v1,v2,6))</span><br><span class="line">V14--&gt;V32</span><br><span class="line">V32--&gt;V34</span><br><span class="line">V34--&gt;V12</span><br><span class="line">V12--&gt;V35</span><br><span class="line">V35--&gt;V65</span><br></pre></td></tr></table></figure><h6 id="第四次构造"><a class="markdownIt-Anchor" href="#第四次构造"></a> 第四次构造</h6><p>队首<code>&lt;v1,v4&gt;</code>出队，构造边，将该边<code>&lt;v1,v4&gt;</code>加入到N集，注意此时由于<code>&lt;v1,v4&gt;</code>加入N集中会构成连通，<strong>所以跳过本次构造边</strong>。</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">V1--1---V3</span><br><span class="line">V3--4---V6</span><br><span class="line">V6--2---V4</span><br><span class="line">V1--5---V4</span><br></pre></td></tr></table></figure><p>所以，当前N集中的边还是和原来一样，如下图：</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">V1--1---V3</span><br><span class="line">V3--4---V6</span><br><span class="line">V6--2---V4</span><br></pre></td></tr></table></figure><p>将<code>V4</code>的除N集中已有的邻接节点入队,发现v4的邻接顶点都在N集中了，所以没有顶点入队</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V65((V6,V5,6))</span><br><span class="line">	V32((v3,v2,5))</span><br><span class="line">	V34((v3,v4,5))</span><br><span class="line">	V35((v3,v5,6))</span><br><span class="line">	V12((v1,v2,6))</span><br><span class="line">V32--&gt;V34</span><br><span class="line">V34--&gt;V12</span><br><span class="line">V12--&gt;V35</span><br><span class="line">V35--&gt;V65</span><br></pre></td></tr></table></figure><h6 id="第五次构造"><a class="markdownIt-Anchor" href="#第五次构造"></a> 第五次构造</h6><p>队首<code>&lt;v3,v2&gt;</code>出队，构造边，将该边加入到N集中。</p><p>此时N集就有五条边了</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">V1--1---V3</span><br><span class="line">V3--4---V6</span><br><span class="line">V6--2---V4</span><br><span class="line">V3--5---V2</span><br></pre></td></tr></table></figure><p>将<code>V2</code>的除N集中已有的邻接节点入队</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V65((V6,V5,6))</span><br><span class="line">	V32((v3,v2,5))</span><br><span class="line">	V34((v3,v4,5))</span><br><span class="line">	V35((v3,v5,6))</span><br><span class="line">	V12((v1,v2,6))</span><br><span class="line">	V25((V2,V5,3))</span><br><span class="line">V32--&gt;V34</span><br><span class="line">V34--&gt;V12</span><br><span class="line">V12--&gt;V35</span><br><span class="line">V35--&gt;V65</span><br><span class="line">V25--&gt;V32</span><br></pre></td></tr></table></figure><h6 id="第六次构造"><a class="markdownIt-Anchor" href="#第六次构造"></a> 第六次构造</h6><p>队首<code>&lt;v2,v5&gt;</code>出队，构造边，加入边到N集中。此时N集中有5条边。由于总共就6个顶点，当构成最小生成树的时候边只能是5条，你如果在加一条边就连通了，所以prim构造生成树结束</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V5((V5))</span><br><span class="line">V1--1---V3</span><br><span class="line">V3--4---V6</span><br><span class="line">V6--2---V4</span><br><span class="line">V3--5---V2</span><br><span class="line">V2--3---V5</span><br></pre></td></tr></table></figure><h6 id="最终结果"><a class="markdownIt-Anchor" href="#最终结果"></a> 最终结果</h6><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V5((V5))</span><br><span class="line">V1--1---V3</span><br><span class="line">V3--4---V6</span><br><span class="line">V6--2---V4</span><br><span class="line">V3--5---V2</span><br><span class="line">V2--3---V5</span><br></pre></td></tr></table></figure><h4 id="算法实现-3"><a class="markdownIt-Anchor" href="#算法实现-3"></a> 算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># prim算法，最小生成树，前提该图必须是连通网</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">prim</span>(<span class="params">self, start</span>):</span></span><br><span class="line">     <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(start):</span><br><span class="line">         <span class="keyword">raise</span> GraphError(<span class="string">&quot;不存在&quot;</span> + start + <span class="string">&quot;这样的顶点&quot;</span>)</span><br><span class="line">     result = GraphAL(&#123;&#125;)</span><br><span class="line">     edgeCount = <span class="number">0</span></span><br><span class="line">     pqueue = []  <span class="comment"># 优先级队列,候选列表</span></span><br><span class="line">     <span class="comment"># 初始化优先级队列</span></span><br><span class="line">     <span class="keyword">for</span> node <span class="keyword">in</span> self._graph[start]:</span><br><span class="line">         heapq.heappush(pqueue, (self._graph[start][node], start, node))</span><br><span class="line">         <span class="keyword">pass</span></span><br><span class="line">     <span class="keyword">while</span> edgeCount &lt; self.get_vertexNum() - <span class="number">1</span> <span class="keyword">and</span> <span class="keyword">not</span> pqueue.__len__() == <span class="number">0</span>:</span><br><span class="line">         <span class="comment"># 出队</span></span><br><span class="line">         pair = heapq.heappop(pqueue)</span><br><span class="line">         distance = pair[<span class="number">0</span>]</span><br><span class="line">         start = pair[<span class="number">1</span>]</span><br><span class="line">         end = pair[<span class="number">2</span>]</span><br><span class="line">         <span class="comment"># 判断是否有该顶点,如果没有就要加入</span></span><br><span class="line">         <span class="keyword">if</span> start <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">             result.add_vertex(start)</span><br><span class="line">         <span class="keyword">if</span> end <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">             result.add_vertex(end)</span><br><span class="line">         <span class="comment"># 如果当前点与下一节点未建立边，则尝试建立边</span></span><br><span class="line">         <span class="comment"># 方式是检查下一节点是否在result中，如果有则说明这个节点已经建立过边了，再建立边的话会可能会形成连通，因此直接舍弃该边的建立</span></span><br><span class="line">         <span class="keyword">if</span> end <span class="keyword">not</span> <span class="keyword">in</span> result._graph[start]:</span><br><span class="line">             <span class="comment"># 如果下一个节点如果未被其他节点连接则result._graph[end]返回false，开始构造边，</span></span><br><span class="line">             <span class="comment"># 如果下一个节点已经被连接了，则result._graph[end]返回true，舍弃该边的建立</span></span><br><span class="line">             <span class="keyword">if</span> <span class="keyword">not</span> result._graph[end]:</span><br><span class="line">                 result.add_edge(start, end, distance)</span><br><span class="line">                 edgeCount += <span class="number">1</span></span><br><span class="line">                 <span class="keyword">pass</span></span><br><span class="line">         start = end</span><br><span class="line">         <span class="comment"># 子节点入队</span></span><br><span class="line">         <span class="keyword">for</span> node <span class="keyword">in</span> self._graph[start]:</span><br><span class="line">             <span class="keyword">if</span> node <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">                 heapq.heappush(pqueue, (self._graph[start][node], start, node))</span><br><span class="line">         <span class="keyword">pass</span></span><br><span class="line">     <span class="keyword">return</span> result</span><br></pre></td></tr></table></figure><h4 id="测试-3"><a class="markdownIt-Anchor" href="#测试-3"></a> 测试</h4><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMDIyNDIzOS5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190830224239"></p><p>与刚才流程构造的结果一致</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V5((V5))</span><br><span class="line">V1--1---V3</span><br><span class="line">V3--4---V6</span><br><span class="line">V6--2---V4</span><br><span class="line">V3--5---V2</span><br><span class="line">V2--3---V5</span><br></pre></td></tr></table></figure><h3 id="克鲁斯卡尔算法"><a class="markdownIt-Anchor" href="#克鲁斯卡尔算法"></a> 克鲁斯卡尔算法</h3><h4 id="算法原理及流程"><a class="markdownIt-Anchor" href="#算法原理及流程"></a> 算法原理及流程</h4><h5 id="原理-2"><a class="markdownIt-Anchor" href="#原理-2"></a> 原理</h5><p>在一个连通图中不断选取权值最小的边，然后连起来，就是这样。</p><p>假设给定图G，结果图T</p><p>基本步骤如下：</p><ol><li>将G中的所有边按权值递增的顺序进行排序</li><li>选择权值最短的边且边的两端点属于不同连通分量（如果两端点属于同一个连通分量中，那么就说明该子图是连通图！所以不行），然后该边与T中已选择的边进行连接，每次边连接都会使得T的连通分量减1</li><li>当边数小于顶点数时，不断重复1,2</li></ol><p>如果当做完上面这些步骤后，得出的结果T中不能包含G中的所有顶点，则说明原图G是不连通的（也就是不是任意一个节点到另一个节点都走的通）</p><p>这里有两个难点：</p><ol><li><p>最短边的选取</p><p>思路①：采用优先队列，在python中可以通过优先级队列实现，其他语言像C++,Java中也有类似实现的数据结构。</p><p>思路②：不断的扫描候选边列表，然后进行排序。这种方法就比较麻烦了，写的代码比较多，不过也很灵活，具体排序方式你可以选择。</p></li><li><p>如何判断边的两个端点的连通分量</p><p>思路①：不断的检查两个端点之间是否有路径，有路径就说明在同一个子图中，连通分量相同。不过这样也太麻烦了点还浪费计算时间</p><p>思路②：前人提出的一种方法，为每个连通分量确定一个代表元，如果两个顶点的代表元相同，则表示他们连通成环。例如下图</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TD</span><br><span class="line">	V1((v1))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V4((V4))</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure><p>当初始化的时候<code>v1,v2,v3,v4</code>的代表元就是他们的序号也就对应<code>0,1,2,3</code></p><p>当<code>v1</code> <code>v2</code> 构成新边的时候，就要把<code>v2</code>的代表元改为<code>v1</code> 的代表元<code>0</code> 。</p><p>这时候<code>v1,v2,v3,v4</code>的代表元就更新为<code>0,0,2,3</code></p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">graph TD</span><br><span class="line">	V1((v1))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V4((V4))</span><br><span class="line">V1---V2</span><br></pre></td></tr></table></figure><p><code>v1</code> <code>v2</code>是的连通分量相同并且他们的代表元也是相同的。</p><p>类似，如果想要连接<code>v2</code> <code>v3</code>，此时<code>v2</code> <code>v3</code> 的代表元不同，因此连接了也不会构成环。 直接把<code>v3</code>的代表元修改为<code>v2</code>的代表元即可，即<code>0</code></p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V4((V4))</span><br><span class="line">V1---V2</span><br><span class="line">V2---V3</span><br></pre></td></tr></table></figure><p>此时<code>v1</code> <code>v2</code> <code>v3</code>是连通的，他们的代表元是<code>0,0,0</code></p><p>如果下一次操作中，想要把<code>v3</code> 连接到<code>v1</code> ，检查他们的代表元，都是<code>0</code>所以连接起来一定会构成环</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V4((V4))</span><br><span class="line">V1---V2</span><br><span class="line">V2---V3</span><br><span class="line">V3---V1</span><br></pre></td></tr></table></figure><p>因此，可以使用代表元判断欲加入的边是否会与已选择集合T中的边构成环路。</p></li></ol><h5 id="构成过程举例"><a class="markdownIt-Anchor" href="#构成过程举例"></a> 构成过程举例</h5><p>假设还是之前的这颗图G，其结果集T中目前还为空</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">graph RL</span><br><span class="line">	V1((V1))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V5((V5))</span><br><span class="line">	V6((V6))</span><br><span class="line">V1--6---V2</span><br><span class="line">V1--1---V3</span><br><span class="line">V1--5---V4</span><br><span class="line">V2--5---V3</span><br><span class="line">V3--5---V4</span><br><span class="line">V3--6---V5</span><br><span class="line">V3--4---V6</span><br></pre></td></tr></table></figure><h6 id="初始化"><a class="markdownIt-Anchor" href="#初始化"></a> 初始化</h6><p>全部边入队，自动在优先队列中根据权值排好序</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	v46((v4,v6,2))</span><br><span class="line">	v56((V5,V6,6))</span><br><span class="line">	v32((v2,v3,5))</span><br><span class="line">	v34((v3,v4,5))</span><br><span class="line">	v35((v3,v5,6))</span><br><span class="line">	v36((v3,v6,4))</span><br><span class="line">	v25((v2,v5,3))</span><br><span class="line">	v14((v1,v4,5))</span><br><span class="line">	v12((v1,v2,6))</span><br><span class="line">	v13((v1,v3,1))</span><br><span class="line">v13---v46</span><br><span class="line">v46---v25</span><br><span class="line">v25---v36</span><br><span class="line">v36---v14</span><br><span class="line">v14---v34</span><br><span class="line">v34---v32</span><br><span class="line">v32---v12</span><br><span class="line">v12---v35</span><br><span class="line">v35---v56</span><br></pre></td></tr></table></figure><p>并且初始化代表元列表，初始值为他们的下标。</p><p>例如<code>v1</code>的代表元初始值为1，<code>v2</code>的代表元初始值为2…<code>vn</code>的代表元初始值为n</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph BT</span><br><span class="line">	v1[v1,1]</span><br><span class="line">	v2[v2,2]</span><br><span class="line">	v3[v3,3]</span><br><span class="line">	v4[v4,4]</span><br><span class="line">	v5[v5,5]</span><br><span class="line">	v6[v6,6]</span><br></pre></td></tr></table></figure><h6 id="第一次构造-2"><a class="markdownIt-Anchor" href="#第一次构造-2"></a> 第一次构造</h6><ol><li>队首出队，所以<code>&lt;v1,v3&gt;</code>边出队</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	v64((v6,v4,2))</span><br><span class="line">	v65((V6,V5,6))</span><br><span class="line">	v32((v3,v2,5))</span><br><span class="line">	v34((v3,v4,5))</span><br><span class="line">	v35((v3,v5,6))</span><br><span class="line">	v36((v3,v6,4))</span><br><span class="line">	v25((v2,v5,3))</span><br><span class="line">	v14((v1,v4,5))</span><br><span class="line">	v12((v1,v2,6))</span><br><span class="line">	v13((v1,v3,1))</span><br><span class="line">v13---v64</span><br><span class="line">v64---v25</span><br><span class="line">v25---v36</span><br><span class="line">v36---v14</span><br><span class="line">v14---v34</span><br><span class="line">v34---v32</span><br><span class="line">v32---v12</span><br><span class="line">v12---v35</span><br><span class="line">v35---v65</span><br></pre></td></tr></table></figure><ol><li>检查<code>v1</code> <code>v3</code>的代表元，很明显不同,所以将<code>&lt;v1,v3&gt;</code>加入T集合中</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">V1--1---V3</span><br></pre></td></tr></table></figure><ol start="3"><li>合并代表元,修改等于代表元值为3的代表元的值，改为<code>v1</code>的代表元即1</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph BT</span><br><span class="line">	v1[v1,1]</span><br><span class="line">	v2[v2,2]</span><br><span class="line">	v3[v3,1]</span><br><span class="line">	v4[v4,4]</span><br><span class="line">	v5[v5,5]</span><br><span class="line">	v6[v6,6]</span><br></pre></td></tr></table></figure><h6 id="第二次构造-2"><a class="markdownIt-Anchor" href="#第二次构造-2"></a> 第二次构造</h6><ol><li>队首出队，所以<code>&lt;v4,v6&gt;</code>边出队</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	v46((v4,v6,2))</span><br><span class="line">	v56((V5,V6,6))</span><br><span class="line">	v32((v2,v3,5))</span><br><span class="line">	v34((v3,v4,5))</span><br><span class="line">	v35((v3,v5,6))</span><br><span class="line">	v36((v3,v6,4))</span><br><span class="line">	v25((v2,v5,3))</span><br><span class="line">	v14((v1,v4,5))</span><br><span class="line">	v12((v1,v2,6))</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">v46---v25</span><br><span class="line">v25---v36</span><br><span class="line">v36---v14</span><br><span class="line">v14---v34</span><br><span class="line">v34---v32</span><br><span class="line">v32---v12</span><br><span class="line">v12---v35</span><br><span class="line">v35---v56</span><br></pre></td></tr></table></figure><ol start="2"><li>检查<code>v4</code> <code>v6</code>的代表元，很明显不同,所以将<code>&lt;v4,v6&gt;</code>加入T集合中</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">V1--1---V3</span><br><span class="line">V6--2---V4</span><br></pre></td></tr></table></figure><ol start="3"><li>合并代表元,修改等于代表元值为6的代表元的值，改为<code>v4</code>的代表元的值即4</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph BT</span><br><span class="line">	v1[v1,1]</span><br><span class="line">	v2[v2,2]</span><br><span class="line">	v3[v3,1]</span><br><span class="line">	v4[v4,4]</span><br><span class="line">	v5[v5,5]</span><br><span class="line">	v6[v6,4]</span><br></pre></td></tr></table></figure><h6 id="第三次构造-2"><a class="markdownIt-Anchor" href="#第三次构造-2"></a> 第三次构造</h6><ol><li>队首出队，所以<code>&lt;v2,v5&gt;</code>边出队</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	v56((V5,V6,6))</span><br><span class="line">	v32((v3,v2,5))</span><br><span class="line">	v34((v3,v4,5))</span><br><span class="line">	v35((v3,v5,6))</span><br><span class="line">	v36((v3,v6,4))</span><br><span class="line">	v25((v2,v5,3))</span><br><span class="line">	v14((v1,v4,5))</span><br><span class="line">	v12((v1,v2,6))</span><br><span class="line">v25---v36</span><br><span class="line">v36---v14</span><br><span class="line">v14---v34</span><br><span class="line">v34---v32</span><br><span class="line">v32---v12</span><br><span class="line">v12---v35</span><br><span class="line">v35---v56</span><br></pre></td></tr></table></figure><ol start="2"><li>检查<code>v2</code> <code>v5</code>的代表元，很明显不同,所以将<code>&lt;v2,v5&gt;</code>加入T集合中</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">graph TD</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V5((V5))</span><br><span class="line">V1--1---V3</span><br><span class="line">V6--2---V4</span><br><span class="line">V2--3---V5</span><br></pre></td></tr></table></figure><ol start="3"><li>合并代表元,修改等于代表元值为5的代表元的值，改为<code>v2</code>的代表元的值即2</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph BT</span><br><span class="line">	v1[v1,1]</span><br><span class="line">	v2[v2,2]</span><br><span class="line">	v3[v3,1]</span><br><span class="line">	v4[v4,4]</span><br><span class="line">	v5[v5,2]</span><br><span class="line">	v6[v6,4]</span><br></pre></td></tr></table></figure><h6 id="第三次构造-3"><a class="markdownIt-Anchor" href="#第三次构造-3"></a> 第三次构造</h6><ol><li>队首<code>&lt;v3,v6&gt;</code>出队</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	v56((v5,V6,6))</span><br><span class="line">	v32((v3,v2,5))</span><br><span class="line">	v34((v3,v4,5))</span><br><span class="line">	v35((v3,v5,6))</span><br><span class="line">	v36((v3,v6,4))</span><br><span class="line">	v14((v1,v4,5))</span><br><span class="line">	v12((v1,v2,6))</span><br><span class="line">v36---v14</span><br><span class="line">v14---v34</span><br><span class="line">v34---v32</span><br><span class="line">v32---v12</span><br><span class="line">v12---v35</span><br><span class="line">v35---v56</span><br></pre></td></tr></table></figure><ol start="2"><li>检查<code>v3</code> <code>v6</code>的代表元，不同,所以将<code>&lt;v3,v6&gt;</code>加入T集合中</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V5((V5))</span><br><span class="line">V1--1---V3</span><br><span class="line">V6--2---V4</span><br><span class="line">V2--3---V5</span><br><span class="line">V3--4---V6</span><br></pre></td></tr></table></figure><ol start="3"><li>合并代表元,修改等于代表元值为4的代表元的值，改为<code>v3</code>代表元的值即1</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph BT</span><br><span class="line">	v1[v1,1]</span><br><span class="line">	v2[v2,2]</span><br><span class="line">	v3[v3,1]</span><br><span class="line">	v4[v4,1]</span><br><span class="line">	v5[v5,2]</span><br><span class="line">	v6[v6,1]</span><br></pre></td></tr></table></figure><h6 id="第四次构造-2"><a class="markdownIt-Anchor" href="#第四次构造-2"></a> 第四次构造</h6><ol><li>队首<code>&lt;v1,v4&gt;</code>出队</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	v56((V5,V6,6))</span><br><span class="line">	v32((v3,v2,5))</span><br><span class="line">	v34((v3,v4,5))</span><br><span class="line">	v35((v3,v5,6))</span><br><span class="line">	v14((v1,v4,5))</span><br><span class="line">	v12((v1,v2,6))</span><br><span class="line">v14---v34</span><br><span class="line">v34---v32</span><br><span class="line">v32---v12</span><br><span class="line">v12---v35</span><br><span class="line">v35---v56</span><br></pre></td></tr></table></figure><ol start="2"><li>检查<code>v1</code> <code>v4</code>的代表元，相同,所以不将<code>&lt;v1,v4&gt;</code>加入T集合中</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V5((V5))</span><br><span class="line">V1--1---V3</span><br><span class="line">V6--2---V4</span><br><span class="line">V2--3---V5</span><br><span class="line">V3--4---V6</span><br><span class="line"></span><br></pre></td></tr></table></figure><ol start="3"><li>此时代表元不进行任何操作</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph BT</span><br><span class="line">	v1[v1,1]</span><br><span class="line">	v2[v2,2]</span><br><span class="line">	v3[v3,1]</span><br><span class="line">	v4[v4,1]</span><br><span class="line">	v5[v5,2]</span><br><span class="line">	v6[v6,1]</span><br></pre></td></tr></table></figure><h6 id="第五次构造-2"><a class="markdownIt-Anchor" href="#第五次构造-2"></a> 第五次构造</h6><ol><li>队首<code>&lt;v3,v4&gt;</code>出队</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	v56((V5,V6,6))</span><br><span class="line">	v32((v3,v2,5))</span><br><span class="line">	v34((v3,v4,5))</span><br><span class="line">	v35((v3,v5,6))</span><br><span class="line">	v12((v1,v2,6))</span><br><span class="line">v34---v32</span><br><span class="line">v32---v12</span><br><span class="line">v12---v35</span><br><span class="line">v35---v56</span><br></pre></td></tr></table></figure><ol start="2"><li>检查<code>v3</code> <code>v4</code>的代表元，相同，所以不将<code>&lt;v3,v4&gt;</code>加入T集合中</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V5((V5))</span><br><span class="line">V1--1---V3</span><br><span class="line">V6--2---V4</span><br><span class="line">V2--3---V5</span><br><span class="line">V3--4---V6</span><br></pre></td></tr></table></figure><ol start="3"><li>此时代表元不进行任何操作</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph BT</span><br><span class="line">	v1[v1,1]</span><br><span class="line">	v2[v2,2]</span><br><span class="line">	v3[v3,1]</span><br><span class="line">	v4[v4,1]</span><br><span class="line">	v5[v5,2]</span><br><span class="line">	v6[v6,1]</span><br></pre></td></tr></table></figure><h6 id="第六次构造-2"><a class="markdownIt-Anchor" href="#第六次构造-2"></a> 第六次构造</h6><ol><li><code>&lt;v2,v3&gt;</code>出队</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	v56((V5,V6,6))</span><br><span class="line">	v32((v3,v2,5))</span><br><span class="line">	v35((v3,v5,6))</span><br><span class="line">	v12((v1,v2,6))</span><br><span class="line">v32---v12</span><br><span class="line">v12---v35</span><br><span class="line">v35---v56</span><br></pre></td></tr></table></figure><ol start="2"><li>检查<code>v2</code> <code>v3</code>的代表元，不同，所以将<code>&lt;v2,v3&gt;</code>加入T集合中</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V5((V5))</span><br><span class="line">V1--1---V3</span><br><span class="line">V6--2---V4</span><br><span class="line">V2--3---V5</span><br><span class="line">V3--4---V6</span><br><span class="line">V3--5---V2</span><br></pre></td></tr></table></figure><ol start="3"><li>合并代表元,修改等于代表元为2的代表元的值，改为<code>v3</code>代表元的值即1</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph BT</span><br><span class="line">	v1[v1,1]</span><br><span class="line">	v2[v2,1]</span><br><span class="line">	v3[v3,1]</span><br><span class="line">	v4[v4,1]</span><br><span class="line">	v5[v5,1]</span><br><span class="line">	v6[v6,1]</span><br></pre></td></tr></table></figure><p>可以发现，当前T集合中已经有5条边了，最小生成树已经生成完毕。同时观察到，代表元中的值也相同了，表示他们都在同一个子图中了。</p><h4 id="算法实现-4"><a class="markdownIt-Anchor" href="#算法实现-4"></a> 算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># kruskal算法，最小生成树，前提该图必须是连通网</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">kruskal</span>(<span class="params">self</span>):</span></span><br><span class="line">    <span class="comment"># 初始化代表元和结果图</span></span><br><span class="line">    result, reps, pqueue, edgesCount = GraphAL(graph=&#123;&#125;), &#123;&#125;, [], <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> key <span class="keyword">in</span> self._graph.keys():</span><br><span class="line">        reps[key] = key</span><br><span class="line">    <span class="comment"># 边入队，按优先级排序,选出最短边</span></span><br><span class="line">    <span class="keyword">for</span> key <span class="keyword">in</span> self._graph:</span><br><span class="line">        <span class="keyword">for</span> end <span class="keyword">in</span> self._graph[key].keys():</span><br><span class="line">            edges = self._graph[key][end]</span><br><span class="line">            heapq.heappush(pqueue, (edges, key, end))  <span class="comment"># 边入队</span></span><br><span class="line">        <span class="keyword">pass</span></span><br><span class="line">    <span class="comment"># 当边数达到n-1条时，即成功得到最小生成树时停止</span></span><br><span class="line">    <span class="keyword">while</span> edgesCount &lt; self.get_vertexNum() - <span class="number">1</span> <span class="keyword">and</span> <span class="keyword">not</span> pqueue.__len__() == <span class="number">0</span>:</span><br><span class="line">        <span class="comment"># 出队</span></span><br><span class="line">        pair = <span class="built_in">list</span>(heapq.heappop(pqueue))</span><br><span class="line">        <span class="comment"># 判断是否有该顶点,如果没有就要加入</span></span><br><span class="line">        <span class="keyword">if</span> pair[<span class="number">1</span>] <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">            result.add_vertex(pair[<span class="number">1</span>])</span><br><span class="line">        <span class="keyword">if</span> pair[<span class="number">2</span>] <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">            result.add_vertex(pair[<span class="number">2</span>])</span><br><span class="line">        <span class="comment"># 检查两点是否属于不同连通分量</span></span><br><span class="line">        <span class="keyword">if</span> reps[pair[<span class="number">1</span>]] != reps[pair[<span class="number">2</span>]]:</span><br><span class="line">            result.add_edge(pair[<span class="number">1</span>], pair[<span class="number">2</span>], pair[<span class="number">0</span>])</span><br><span class="line">            edgesCount += <span class="number">1</span></span><br><span class="line">            <span class="comment"># 合并连通分量</span></span><br><span class="line">            rep, orep = reps[pair[<span class="number">1</span>]], reps[pair[<span class="number">2</span>]]</span><br><span class="line">            <span class="keyword">for</span> key <span class="keyword">in</span> reps.keys():</span><br><span class="line">                <span class="keyword">if</span> reps[key] == orep:</span><br><span class="line">                    reps[key] = rep</span><br><span class="line">    <span class="keyword">return</span> result</span><br><span class="line">    <span class="keyword">pass</span></span><br></pre></td></tr></table></figure><h4 id="测试-4"><a class="markdownIt-Anchor" href="#测试-4"></a> 测试</h4><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTAwMjYzNC5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190831002634"></p><p>与刚才结果自动推的完全一致。</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	V1((v1))</span><br><span class="line">	V3((V3))</span><br><span class="line">	V6((V6))</span><br><span class="line">	V4((V4))</span><br><span class="line">	V2((V2))</span><br><span class="line">	V5((V5))</span><br><span class="line">V1--1---V3</span><br><span class="line">V6--2---V4</span><br><span class="line">V2--3---V5</span><br><span class="line">V3--4---V6</span><br><span class="line">V3--5---V2</span><br></pre></td></tr></table></figure><h2 id="最短路径"><a class="markdownIt-Anchor" href="#最短路径"></a> 最短路径</h2><h3 id="dijkstra算法"><a class="markdownIt-Anchor" href="#dijkstra算法"></a> dijkstra算法</h3><h4 id="算法原理"><a class="markdownIt-Anchor" href="#算法原理"></a> 算法原理</h4><p>在看迪杰斯特拉算法之前，可以先回顾下BFS算法的过程。BFS的实现是通过一个队列实现。还是这张图</p><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgyNTE2MDMwNS5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190825160305"></p><p>选择假设BFS从A节点开始，A节点出队后，将A的邻接节点B,C入队</p><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTE5MDkzNy5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190831190937"></p><p>然后B出队，D入队，C出队，E入队。整个BFS的流程大概如此，在这之中，可以看到BFS队列中不同节点离A的距离，每个出队的结点对于他的邻接节点的距离都是1，并且在队列中他们也是紧紧挨着的。</p><p>假如可以把这些顶点进行排序，然后不断更新队中节点到A的距离值，那么应该可以一步步的获得当前节点到A节点的最短距离了。</p><p>该算法有两个难点：</p><ol><li>如何排序</li></ol><p>我使用的是python的优先队列，该队列是基于堆这一种数据结构实现的，你也可以自行选择排序算法进行排序</p><ol start="2"><li>如何更新距离</li></ol><p>在BFS中每个节点到A的距离是固定的，是不会发生更新操作的，这是由于BFS算法实现过程中有个访问标志会标志某个节点是否已被访问，该标志保证了每个节点只访问一次。但是在迪杰斯特拉算法中，这样是不行的，因为想要在每个节点出队后，都要将该结点的邻接节点到目标点（这个例子中是A点）的距离进行比较更新，选择权值和小的。</p><p>看下面这个网</p><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTE5MzUyMC5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190831193520"></p><p>当遍历到B的时候A到B有两条路，一条是A-B，另一条是A-C-B，前者的距离为5，比较长，后者的距离为3（1+2）。在迪杰斯特拉中就会选择路径A-C-B这条路径。</p><p>在实际的算法实现中，距离的比较是通过一个<code>distance</code>的列表实现的，该列表距离了每个顶点到目标点的最短距离。然后在下一次遍历中不断得更新这个距离就可以了。</p><h5 id="构造过程举例-2"><a class="markdownIt-Anchor" href="#构造过程举例-2"></a> 构造过程举例</h5><p>假设还是上面这个图。</p><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTE5MzUyMC5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190831193520"></p><p>要求图中顶点到A的最短距离</p><h6 id="初始化-2"><a class="markdownIt-Anchor" href="#初始化-2"></a> 初始化</h6><p>初始化距离列表,inf 表示无穷，A的目标点，所以距离为0</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A[A,0]</span><br><span class="line">	B[B,inf]</span><br><span class="line">	C[C,inf]</span><br><span class="line">	D[D,inf]</span><br><span class="line">	E[E,inf]</span><br><span class="line">	F[F,inf]</span><br></pre></td></tr></table></figure><p>初始化优先级队列，目标节点A入队</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A((A,0))</span><br></pre></td></tr></table></figure><p>当队列不为空时，循环。</p><h6 id="第一次构造-3"><a class="markdownIt-Anchor" href="#第一次构造-3"></a> 第一次构造</h6><ol><li>A出队,并标记为已访问，遍历A的邻接节点B、C，同时将A到B的距离5(0+5)和A到C的距离1(0+1)，与<code>distance</code>列表中的距离进行比较，由于<code>distance</code>中的距离都是无穷，所以<code>distance</code>中C的距离更新为1，B的距离更新为<code>5</code></li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A[A,0]</span><br><span class="line">	B[B,5]</span><br><span class="line">	C[C,1]</span><br><span class="line">	D[D,inf]</span><br><span class="line">	E[E,inf]</span><br><span class="line">	F[F,inf]</span><br></pre></td></tr></table></figure><ol start="2"><li>B,C节点由于距离被更新了。需要参与下一次比较，所以B、C入队</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	B((B,5))</span><br><span class="line">	C((C,1))</span><br><span class="line">C--&gt;B</span><br></pre></td></tr></table></figure><p>第二次构造</p><ol><li>C出队，并标记为已访问，遍历C的邻接节点A,B,D,E，将C-A的距离1，C-B的距离3(1+2)和C-D的距离5(1+4)和C-E的距离9（1+8），与<code>distance</code>列表中的B,C,E的距离进行比较，更新为其中的较小值</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A[A,0]</span><br><span class="line">	B[B,3]</span><br><span class="line">	C[C,1]</span><br><span class="line">	D[D,5]</span><br><span class="line">	E[E,9]</span><br><span class="line">	F[F,inf]</span><br></pre></td></tr></table></figure><ol start="2"><li>由于B,D,E的距离被更新了。需要参与下一次的比较，所以B,C,E需要入队，带着他们的更新后的权值</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	B((B,5))</span><br><span class="line">	B1((B,3))</span><br><span class="line">	D((D,5))</span><br><span class="line">	E((E,9))</span><br><span class="line"></span><br><span class="line">B1--&gt;B</span><br><span class="line">B--&gt;D</span><br><span class="line">D--&gt;E</span><br></pre></td></tr></table></figure><h6 id="第三次构造-4"><a class="markdownIt-Anchor" href="#第三次构造-4"></a> 第三次构造</h6><ol><li>B出队，并标记为已访问，遍历B的子节点D,C,A，将B-D（3+1=4）,B-C（3+2=5）,B-A（3+5）的距离分别与<code>distance</code>中的D,C,A距离进行比较，取小的值，发现只有D的距离被更新为了4</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A[A,0]</span><br><span class="line">	B[B,3]</span><br><span class="line">	C[C,1]</span><br><span class="line">	D[D,4]</span><br><span class="line">	E[E,9]</span><br><span class="line">	F[F,inf]</span><br></pre></td></tr></table></figure><ol start="3"><li>由于D被更新了，需要参与下一次的比较，所以D入队，带着D更新后的权值</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	D1((D,4))</span><br><span class="line">	B((B,5))</span><br><span class="line">	D((D,5))</span><br><span class="line">	E((E,9))</span><br><span class="line">	</span><br><span class="line">D1--&gt;B</span><br><span class="line">B--&gt;D</span><br><span class="line">D--&gt;E</span><br></pre></td></tr></table></figure><h6 id="第四次构造-3"><a class="markdownIt-Anchor" href="#第四次构造-3"></a> 第四次构造</h6><ol><li>D出队，并标记为已访问，遍历D的子节点B,C,E,F。将D-B（4+1=5）,D-C（4+4=8）,D-E(4+3=7),D-F(4+6=10)的距离分别与<code>distance</code>中的B,C,E,F距离进行比较，取小的值</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A[A,0]</span><br><span class="line">	B[B,3]</span><br><span class="line">	C[C,1]</span><br><span class="line">	D[D,4]</span><br><span class="line">	E[E,7]</span><br><span class="line">	F[F,10]</span><br></pre></td></tr></table></figure><ol start="3"><li>由于只有E,F的距离被更新为7,和10，所以E，F需要带着他们更新后的权值入队，参与下一次的比较。</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line"></span><br><span class="line">	B((B,5))</span><br><span class="line">	D((D,5))</span><br><span class="line">	E1((E,7))</span><br><span class="line">	E((E,9))</span><br><span class="line">	F((F,10))</span><br><span class="line">	</span><br><span class="line">B--&gt;D</span><br><span class="line">D--&gt;E1</span><br><span class="line">E1--&gt;E</span><br><span class="line">E--&gt;F</span><br></pre></td></tr></table></figure><h6 id="第五次构造-3"><a class="markdownIt-Anchor" href="#第五次构造-3"></a> 第五次构造</h6><ol><li>队首B出队，由于B被标记已访问，所以直接扔掉，进入下一个循环</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	D((D,5))</span><br><span class="line">	E1((E,7))</span><br><span class="line">	E((E,9))</span><br><span class="line">	F((F,10))</span><br><span class="line">D--&gt;E1</span><br><span class="line">E1--&gt;E</span><br><span class="line">E--&gt;F</span><br></pre></td></tr></table></figure><ol start="2"><li>队首D出队，由于D已经被标记已访问，扔掉。进入下一个循环</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line"></span><br><span class="line">    E1((E,7))</span><br><span class="line">	E((E,9))</span><br><span class="line">	F((F,10))</span><br><span class="line"></span><br><span class="line">E1--&gt;E</span><br><span class="line">E--&gt;F</span><br></pre></td></tr></table></figure><ol start="3"><li><p>队首E出队，标记为已访问。遍历其邻接节点C,D，将E-C（7+4=11），E-D（7+3=10）与<code>distance</code>中的C,D值进行比较，取小的值，发现C,D都不需要更新。</p></li><li><p>由于没有节点被更新，所以没有节点入队。此时的<code>distance</code>如下图</p></li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A[A,0]</span><br><span class="line">	B[B,3]</span><br><span class="line">	C[C,1]</span><br><span class="line">	D[D,4]</span><br><span class="line">	E[E,7]</span><br><span class="line">	F[F,10]</span><br></pre></td></tr></table></figure><h6 id="第六次构造-3"><a class="markdownIt-Anchor" href="#第六次构造-3"></a> 第六次构造</h6><ol><li>队首E出队，由于E被标记为已访问，扔掉，进入下一个循环</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	E((E,9))</span><br><span class="line">	F((F,10))</span><br><span class="line"></span><br><span class="line">E--&gt;F</span><br></pre></td></tr></table></figure><ol start="2"><li>队首E出队，由于E被标记为已访问，扔掉，进入下一个循环</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">graph LR</span><br><span class="line">	F((F,10))</span><br></pre></td></tr></table></figure><ol start="3"><li>队首F出队,发现他没有子节点，所以<code>distance</code>不会被更新，队列将不会加入新的结点。此时的<code>distance</code>如下图</li></ol><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A[A,0]</span><br><span class="line">	B[B,3]</span><br><span class="line">	C[C,1]</span><br><span class="line">	D[D,4]</span><br><span class="line">	E[E,7]</span><br><span class="line">	F[F,10]</span><br></pre></td></tr></table></figure><h6 id="第七次构造"><a class="markdownIt-Anchor" href="#第七次构造"></a> 第七次构造</h6><p>由于此时队列为空，所以循环结束，迪杰斯特拉算法求解完毕！此时的<code>distance</code>就是每个节点到目标点A的最短距离了。</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A[A,0]</span><br><span class="line">	B[B,3]</span><br><span class="line">	C[C,1]</span><br><span class="line">	D[D,4]</span><br><span class="line">	E[E,7]</span><br><span class="line">	F[F,10]</span><br></pre></td></tr></table></figure><p>迪杰斯特拉算法就是基于这种&quot;宽度优先遍历&quot;的思想，按路径的长度选择下一个最短节点然后逐步扩张（这一点也很像用MST性质实现的prim算法）。这个算法在探索中也会更新已经节点的最短路径，每一步都可以找到一个确定的最短路径，这就是典型的动态规划思想（在计算中保留一些信息，用来支持下一步的决策信息）</p><h4 id="算法实现-5"><a class="markdownIt-Anchor" href="#算法实现-5"></a> 算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 迪杰斯特拉法算最短路径</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">dijkstra</span>(<span class="params">self, start</span>):</span></span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(start):</span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">&quot;不存在&quot;</span> + start + <span class="string">&quot;这样的顶点&quot;</span>)</span><br><span class="line">    graph = self._graph</span><br><span class="line">    pqueue = []  <span class="comment"># 优先级队列</span></span><br><span class="line">    heapq.heappush(pqueue, (<span class="number">0</span>, start))  <span class="comment"># 根顶点进队，最高优先级</span></span><br><span class="line">    seen = <span class="built_in">set</span>()  <span class="comment"># 记录访问过的顶点</span></span><br><span class="line">    parent = &#123;start: <span class="literal">None</span>&#125;  <span class="comment"># 生成树</span></span><br><span class="line">    distance = self.__init_distance(start)  <span class="comment"># 初始化距离</span></span><br><span class="line">    <span class="keyword">while</span> pqueue.__len__() &gt; <span class="number">0</span>:</span><br><span class="line">        pair = heapq.heappop(pqueue)  <span class="comment"># pop弹出的是元组，第一个参数是距离（优先级），第二个是顶点</span></span><br><span class="line">        dist = pair[<span class="number">0</span>]</span><br><span class="line">        vertex = pair[<span class="number">1</span>]</span><br><span class="line">        seen.add(vertex)  <span class="comment"># 记录访问过的顶点</span></span><br><span class="line">        nodes = graph[vertex].keys()  <span class="comment"># 获取其顶点的邻接顶点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> nodes:</span><br><span class="line">            <span class="keyword">if</span> node <span class="keyword">not</span> <span class="keyword">in</span> seen:</span><br><span class="line">                <span class="keyword">if</span> dist + graph[vertex][node] &lt; distance[node]:  <span class="comment"># 如果当前顶点到开始顶点的距离小于距离列表中的值，更新距离</span></span><br><span class="line">                    heapq.heappush(pqueue, (dist + graph[vertex][node], node))</span><br><span class="line">                    parent[node] = vertex</span><br><span class="line">                    distance[node] = dist + graph[vertex][node]</span><br><span class="line">        <span class="comment"># 输出遍历结果</span></span><br><span class="line">        <span class="comment"># print(vertex)</span></span><br><span class="line">    <span class="keyword">return</span> distance, parent</span><br><span class="line">    <span class="keyword">pass</span></span><br></pre></td></tr></table></figure><h4 id="测试-5"><a class="markdownIt-Anchor" href="#测试-5"></a> 测试</h4><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTIwNTYzMi5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190831205632"></p><p>可以发现，如刚才推导的结果一模一样。</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">graph TB</span><br><span class="line">	A[A,0]</span><br><span class="line">	B[B,3]</span><br><span class="line">	C[C,1]</span><br><span class="line">	D[D,4]</span><br><span class="line">	E[E,7]</span><br><span class="line">	F[F,10]</span><br></pre></td></tr></table></figure><h3 id="弗洛依德算法待填坑"><a class="markdownIt-Anchor" href="#弗洛依德算法待填坑"></a> 弗洛依德算法(待填坑)</h3><h4 id="算法原理-2"><a class="markdownIt-Anchor" href="#算法原理-2"></a> 算法原理</h4><h4 id="算法实现-6"><a class="markdownIt-Anchor" href="#算法实现-6"></a> 算法实现</h4><h4 id="测试-6"><a class="markdownIt-Anchor" href="#测试-6"></a> 测试</h4><h2 id="拓扑排序"><a class="markdownIt-Anchor" href="#拓扑排序"></a> 拓扑排序</h2><h3 id="算法原理-3"><a class="markdownIt-Anchor" href="#算法原理-3"></a> 算法原理</h3><p>拓扑排序是有向图（网）中的内容，只在有向网（图）的范畴中讨论。</p><p>先看一个实际生活中可能遇到的问题：选课问题，例如上大一的时候你肯定要先学C语言，然后才能学数据结构。这个时候C语言和数据结构就构成了一个排列问题，<strong>谁在前谁在后</strong>。用图中的顶点表示一个活动，边表示活动之间的顺序关系。这样的图就称为AOV网（顶点活动网）</p><p>下图就是一个典型的AOV网实例。</p><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTIxMDUwMS5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190831210501"></p><p>任何无回路的AOV网N都可以求解出拓扑序列，方法很简单：</p><ul><li>从N中选出一个入度为0的顶点作为序列的下一个顶点</li><li>从N网中删除所选顶点的出边</li><li>重复执行上面两步，直到已经选出了图N的所有顶点</li></ul><p>拓扑排序算法有两个难点：</p><ol><li>如何寻找入度为0的顶点</li><li>真的需要拷贝整张图，然后进行删除</li></ol><p>一个显然的办法是不断遍历图，寻找入度为0的顶点。但时间代价会很高。顶点间的制约关系决定了顶点的入度。入度是一个整数，用一个整数表就能记录所以顶点的入度了。因此，我的方法是用一张入度表记录了每个顶点的入度，初始时，表中的各顶点的入度对应为图中顶点的入度，在随后的计算中，一旦选中一个顶点，就将该顶点的出边入度减一。</p><p>在实际的算法实现中还用了一个0度栈来记录已经入度为0但还未处理的顶点。</p><p>算法比较简单。</p><p>可以慢慢调试</p><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTIxMjIzNi5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190831212236"></p><h3 id="算法实现-7"><a class="markdownIt-Anchor" href="#算法实现-7"></a> 算法实现</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">topological_sort</span>(<span class="params">self</span>):</span></span><br><span class="line">    indegree = &#123;&#125;  <span class="comment"># 入度表</span></span><br><span class="line">    zerov = []  <span class="comment"># 利用0度栈记录已知的入度为0的但还未处理的顶点</span></span><br><span class="line">    m = <span class="number">0</span>  <span class="comment"># 输出顶点计数</span></span><br><span class="line">    topo = []  <span class="comment"># 拓扑排序结果</span></span><br><span class="line">    <span class="comment"># 生成入度表和0度栈</span></span><br><span class="line">    <span class="keyword">for</span> vetx <span class="keyword">in</span> self._graph:</span><br><span class="line">        indegree[vetx] = self.get_inEdge(vetx).__len__()</span><br><span class="line">        <span class="keyword">if</span> indegree[vetx] == <span class="number">0</span>:</span><br><span class="line">            zerov.append(vetx)</span><br><span class="line">        <span class="keyword">pass</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> zerov.__len__() != <span class="number">0</span>:</span><br><span class="line">        Vi = zerov.pop()</span><br><span class="line">        topo.append(Vi)</span><br><span class="line">        m += <span class="number">1</span></span><br><span class="line">        <span class="keyword">for</span> Vj <span class="keyword">in</span> self.get_outEdge(Vi).keys():  <span class="comment"># 对顶点Vi的每个邻接点入度减1，如果Vj的入度变为0，则将Vj入栈，表示Vj就是下一个需要处理的顶点</span></span><br><span class="line">            indegree[Vj] -= <span class="number">1</span></span><br><span class="line">            <span class="keyword">if</span> indegree[Vj] == <span class="number">0</span>:</span><br><span class="line">                zerov.append(Vj)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> m &lt; self.get_vertexNum():  <span class="comment"># 该有向图有回路</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">False</span></span><br><span class="line">    <span class="keyword">return</span> topo</span><br></pre></td></tr></table></figure><h3 id="测试-7"><a class="markdownIt-Anchor" href="#测试-7"></a> 测试</h3><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8xNTY3MjU3ODM1OTQ5LnBuZyFibG9n?x-oss-process=image/format,png" alt="1567257835949"></p><h2 id="关键路径"><a class="markdownIt-Anchor" href="#关键路径"></a> 关键路径</h2><h3 id="算法原理-4"><a class="markdownIt-Anchor" href="#算法原理-4"></a> 算法原理</h3><h3 id="算法实现-8"><a class="markdownIt-Anchor" href="#算法实现-8"></a> 算法实现</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 关键路径</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">criticalPath</span>(<span class="params">self, delay=<span class="number">0</span></span>):</span></span><br><span class="line">    topo = self.topological_sort()</span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> topo:</span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">&quot;存在有向环！&quot;</span>)</span><br><span class="line">    ve = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(topo))]  <span class="comment"># 事件最早开始时间</span></span><br><span class="line">    vl = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(topo))]  <span class="comment"># 事件最迟开始时间</span></span><br><span class="line">    cp = []  <span class="comment"># 关键路径</span></span><br><span class="line">    result = &#123;&#125;  <span class="comment"># 返回结果</span></span><br><span class="line">    <span class="comment"># --------------------------------计算事件的最早发生时间-----------------------------</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(topo.__len__()):</span><br><span class="line">        start = topo[i]  <span class="comment"># 取出拓扑节点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> self.get_outEdge(start).keys():  <span class="comment"># 获取拓扑节点的邻接点，计算ve</span></span><br><span class="line">            w = self._graph[start][node]  <span class="comment"># 当前节点与邻接节点的边</span></span><br><span class="line">            j = topo.index(node)  <span class="comment"># 邻接节点的下标</span></span><br><span class="line">            <span class="keyword">if</span> ve[j] &lt; ve[i] + w:  <span class="comment"># 更新邻接点的最早发生时间，选大的时间</span></span><br><span class="line">                ve[j] = ve[i] + w</span><br><span class="line">            <span class="keyword">pass</span></span><br><span class="line">    <span class="comment"># --------------------------------计算事件的最晚发生时间-----------------------------</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(topo.__len__()):  <span class="comment"># 给每个事件的最迟发生时间置初值，初值为最早发生时间中的最大值</span></span><br><span class="line">        vl[i] = ve[topo.__len__() - <span class="number">1</span>] + delay</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">reversed</span>(<span class="built_in">range</span>(topo.__len__())):</span><br><span class="line">        k = topo[i]  <span class="comment"># 取出拓扑节点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> self.get_inEdge(k).keys():  <span class="comment"># 获取拓扑节点的逆邻接点，计算vl</span></span><br><span class="line">            w = self._graph[node][k]  <span class="comment"># 逆邻接点和当前节点的边</span></span><br><span class="line">            j = topo.index(node)  <span class="comment"># 逆邻接点的下标</span></span><br><span class="line">            <span class="keyword">if</span> vl[j] &gt; vl[i] - w:  <span class="comment"># 更新逆邻接点的最晚发生时间，选小的时间</span></span><br><span class="line">                vl[j] = vl[i] - w</span><br><span class="line">            <span class="keyword">pass</span></span><br><span class="line">    <span class="comment"># --------------------------------判断每一活动是否为关键路径--------------------------</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(topo.__len__()):</span><br><span class="line">        start = topo[i]</span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> self.get_outEdge(start).keys():</span><br><span class="line">            j = topo.index(node)  <span class="comment"># 获得邻接顶点的下标</span></span><br><span class="line">            w = self._graph[start][node]  <span class="comment"># 当前节点与邻接节点的边</span></span><br><span class="line">            e = ve[i]  <span class="comment"># 计算活动&lt;start,node&gt;的最早开始时间</span></span><br><span class="line">            l = vl[j] - w - delay  <span class="comment"># 计算活动&lt;start,node&gt;的最晚开始时间</span></span><br><span class="line">            <span class="keyword">if</span> e == l:</span><br><span class="line">                cp.append((start, node))  <span class="comment"># 如果相等就说明为关键路径</span></span><br><span class="line">            <span class="keyword">pass</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(topo.__len__()):</span><br><span class="line">        result[topo[i]] = (ve[i], vl[i])</span><br><span class="line">        <span class="keyword">pass</span></span><br><span class="line">    <span class="keyword">return</span> result, cp</span><br></pre></td></tr></table></figure><h3 id="测试-8"><a class="markdownIt-Anchor" href="#测试-8"></a> 测试</h3><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly96aG9uZy1ibG9nLm9zcy1jbi1zaGVuemhlbi5hbGl5dW5jcy5jb20vYmxvZy8yMDE5MDgzMTIxMjUwNC5wbmchYmxvZw?x-oss-process=image/format,png" alt="20190831212504"></p></div><div class="article-footer"><blockquote class="mt-2x"><ul class="post-copyright list-unstyled"><li class="post-copyright-link hidden-xs"><strong>本文链接：</strong> <a href="http://xiaozhong233.gitee.io/2020/11/19/%E5%9B%BE%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%EF%BC%88%E6%B1%87%E6%80%BB%EF%BC%89/" target="_blank" rel="external">http://xiaozhong233.gitee.io/2020/11/19/%E5%9B%BE%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%EF%BC%88%E6%B1%87%E6%80%BB%EF%BC%89/</a></li><li class="post-copyright-license"><strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="http://creativecommons.org/licenses/by/4.0/deed.zh" target="_blank" rel="external">CC BY 4.0 CN协议</a> 许可协议。转载请注明出处！</li></ul></blockquote><div class="panel panel-default panel-badger"><div class="panel-body"><figure class="media"><div class="media-left"><a href="https://github.com/XiaoZhong233" target="_blank" class="img-burn thumb-sm visible-lg"><img src="/images/avatar.jpg" class="img-rounded w-full" alt=""></a></div><div class="media-body"><h3 class="media-heading"><a href="https://github.com/XiaoZhong233" target="_blank"><span class="text-dark">钟</span><small class="ml-1x">苦逼学生仔 &amp; 未来搬砖大师</small></a></h3><div>个人简介。</div></div></figure></div></div></div></article><section id="comments"></section></div><nav class="bar bar-footer clearfix" data-stick-bottom><div class="bar-inner"><ul class="pager pull-left"><li class="prev"><a href="/2020/11/19/React%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93/" title="(no title)"><i class="icon icon-angle-left" aria-hidden="true"></i><span>&nbsp;&nbsp;上一篇</span></a></li><li class="next"><a href="/2020/11/19/%E6%B5%85%E8%B0%88%E5%8C%BA%E5%9D%97%E9%93%BE%E7%9A%84%E5%AF%86%E7%A0%81%E5%AD%A6%E5%8E%9F%E7%90%86_hash%E4%B8%8E%E7%AD%BE%E5%90%8D/" title="&#39;浅谈区块链的密码学原理:hash与签名&#39;"><span>下一篇&nbsp;&nbsp;</span><i class="icon icon-angle-right" aria-hidden="true"></i></a></li></ul><div class="bar-right"><div class="share-component" data-sites="weibo,qq,wechat,facebook,twitter" data-mobile-sites="weibo,qq,qzone"></div></div></div></nav></main><footer class="footer" itemscope itemtype="http://schema.org/WPFooter"><ul class="social-links"><li><a href="https://github.com/XiaoZhong233" target="_blank" title="Github" data-toggle="tooltip" data-placement="top"><i class="icon icon-github"></i></a></li><li><a href="/atom.xml" target="_blank" title="Rss" data-toggle="tooltip" data-placement="top"><i class="icon icon-rss"></i></a></li></ul><div class="copyright"><div class="publishby">Theme by <a href="https://github.com/cofess" target="_blank">cofess </a>base on <a href="https://github.com/cofess/hexo-theme-pure" target="_blank">pure</a>.</div></div></footer><script src="//cdn.jsdelivr.net/npm/jquery@1.12.4/dist/jquery.min.js"></script><script>window.jQuery||document.write('<script src="js/jquery.min.js"><\/script>')</script><script src="/js/plugin.min.js"></script><script src="/js/application.js"></script><script>window.INSIGHT_CONFIG={TRANSLATION:{POSTS:"文章",PAGES:"页面",CATEGORIES:"分类",TAGS:"标签",UNTITLED:"(未命名)"},ROOT_URL:"/",CONTENT_URL:"/content.json"}</script><script src="/js/insight.js"></script><script src="//cdn.jsdelivr.net/npm/gitment@0.0.3/dist/gitment.browser.min.js"></script><script>var gitment=new Gitment({id:"",owner:"XiaoZhong233",repo:"blog_comments",oauth:{client_id:"872c8be0e1b0dc0dc59b",client_secret:"9850234f5d5a83d14eecb2fdc74ab4bc8d624287"}});gitment.render("comments")</script></body></html>